public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
 }

class Solution {
    //解法1: 自根向下的递归
    public int helper(TreeNode root) {
        if (root == null) return 0;
        int leftTree = helper(root.left);
        int rightTree = helper(root.right);
        return leftTree > rightTree ? leftTree + 1 : rightTree + 1;
    }
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return Math.abs(helper(root.left)-helper(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }
    //解法2:自下向根的递归
    public boolean isBalanced2(TreeNode root) {
        return helper2(root) >= 0;
    }
    public int helper2(TreeNode root) {
        if (root == null) return 0;
        int left = helper(root.left);
        int right = helper(root.right);
        if (left == -1 || right == -1 || Math.abs(left-right) > 1) return -1;
        return Math.max(left,right) + 1;
    }
}